/**
 * 最多完成k次交易，获得最大利润，但不能同时参与多比交易（即不能在卖出前再次买入）
 * 二维动态规划
 * dp[i][j] = dp[i][j-1](本次不操作)
 *          = price[j] - price[n] + dp[i-1][n](本次价格 - 前第n次的价格 + dp中第n列的上一行的值)(n从 0到j-1)
 *          =>优化计算： maxProfit = max(-price[n] + dp[i-1][n], maxProfit)
 *          =>原式转化为 price[j] + maxProfit
 * @param {number[]} prices 
 */
var maxProfit1 = function (k, prices) {
    if (prices.length === 0) {
        return 0
    }
    // 定义k+1行、prices.length列的二维数组
    // Array.from(arrLike, mapFn) 可以将 类数组对象/可遍历对象 转换为真正的数组
    const dp = Array.from(Array(k + 1), () => new Array(prices.length))

    // 第一行第一列为0
    for (let i = 0; i < prices.length; i++) {
        dp[0][i] = 0
    }
    for (let i = 0; i < k + 1; i++) {
        dp[i][0] = 0
    }

    // 填充剩余的i行j列
    for (let i = 1; i < k + 1; i++) {
        let maxProfit = 0 - prices[0]
        for (let j = 1; j < prices.length; j++) {
            dp[i][j] = Math.max(dp[i][j - 1], prices[j] + maxProfit)

            maxProfit = Math.max(dp[i - 1][j] - prices[j], maxProfit)
        }
    }

    return dp[k][prices.length - 1]
}